//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// nums 按 严格递增 顺序排列 
// 
// Related Topics 树 二叉搜索树 数组 分治 二叉树 
// 👍 866 👎 0

package com.cute.leetcode.editor.cn;
public class ConvertSortedArrayToBinarySearchTree {
    public static void main(String[] args) {
        int[] nums = {-10,-3,0,5,9};
        TreeNode root = new ConvertSortedArrayToBinarySearchTree().new Solution().sortedArrayToBST(nums);
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 需要转换成高度平衡的二叉搜索树，两边最大高度差不超过1
     * 我的思路啊，既然给的数组是严格排序的，那我就找到数组中间值，左边的往左子树添加，右边的往右子树添加就可以了
     * 我这个思路，只是满足了顺序要求，并没有满足二叉搜索树的结构
     *
     * 二叉搜索树的中序遍历结果就是顺序结构，所以以中序遍历的方式进行元素添加就可以了
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        /*if (nums.length ==1) return new TreeNode(nums[0]);
        int rootIndex = nums.length/2;
        TreeNode root = new TreeNode(nums[rootIndex]);
        TreeNode temp = root;
        for (int i = rootIndex-1; i >=0; i--) {
            temp.left = new TreeNode(nums[i]);
            temp = temp.left;
        }
        temp = root;
        for (int i = rootIndex+1; i <nums.length ; i++) {
            temp.right = new TreeNode(nums[i]);
            temp = temp.right;
        }
        return root;*/
        return infixOrder(nums, 0, nums.length-1);
    }

    /**
     * 通过递归按照中序遍历来添加元素
     * 每次递归时传入原始数组以及小区间的初始和结束下标
     * 为了满足平衡二叉树的要求，每次添加的元素是当前小区间的中间值
     * 直到左下标>右下标之后返回null
     */
    public TreeNode infixOrder(int[] nums, int low, int high){
        if (low > high) return null;
        int mid = (low + high)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = infixOrder(nums, low, mid-1);
        root.right = infixOrder(nums, mid+1, high);
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}